//024. 字典排列
//        一个排列是某些对象的有序组合，例如，3124 就是数字 1，2，3，4 的一种可能排列。
//        如果所有的排列按照数值或者字母序排序，我们称其为一个字典序。
//        0, 1, 2 的字典排列有：012 021 102 120 201 210。
//        从 0 到 9 的所有数字构成的字典排列中，第一百万个数字是多少？
//        答案：2783915460

public class Week024 {
    //回溯法
    static final int NUMBER = 10;
    static boolean[] book = new boolean[NUMBER];
    static int[] ans = new int[NUMBER];
    static int n = 1000000;
    static void dfs(int currentNumber) {
        //当n小于0时，说明已经输出了答案
        if (n < 0) return;
        //个数达到NUMBER个
        if (currentNumber == NUMBER) {
            //已经排列到第n个数了
            if (--n == 0) {
                for (int i = 0; i < NUMBER; ++i) {
                    System.out.print(ans[i]);
                }
            }
            return;
        }
        for (int i = 0; i < NUMBER; ++i) {
            //如果该数已经选了，则不对其进行继续的搜索
            if (book[i]) continue;
            //将该数选上，并进行下一步搜索
            book[i] = true;
            ans[currentNumber] = i;
            dfs(currentNumber + 1);
            //回溯
            book[i] = false;
        }
    }
    static void run() {
        //初始已查找到的个数为0
        dfs(0);
    }
    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
